package LeetCode.Leet400_499.Leet410_419.Leet416;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/5/30 9:07
 * @Description TODO: 方法一    动态规划  29ms    53.91%
 */
class Solution_1 {
    // TODO: 转化为0-1背包问题，把背包容量为sum/2的背包装满
    public boolean canPartition(int[] nums) {
        int sum = 0;
        // 求和sum
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        // 为奇数，肯定没有答案
        if (sum % 2 != 0) {
            return false;
        }
        // 0-1背包问题，把背包容量为sum/2的背包装满
        // 物品i占用空间与价值均为nums[i];
        int n = sum / 2;
        // 1. dp含义：容量为j的背包，装前i个物品可以装的最大价值为dp[i][j]
        int[][] dp = new int[nums.length][n + 1];
        // 2. 初始化数组：容量为0，以及装前1个物品的最大价值
        // 2.1 初始化容量为0
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = 0;
        }
        // 2.2 初始化装前1个物品的最大价值
        for (int j = 0; j < n + 1; j++) {
            dp[0][j] = j >= nums[0] ? nums[0] : 0;
        }

        // 3. 遍历数组
        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j < n + 1; j++) {
                // 4. 递推函数
                if (j >= nums[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], nums[i] + dp[i - 1][j - nums[i]]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            // 判断能否把背包容量为sum/2的背包装满
            if (dp[i][n] == n) {
                return true;
            }
        }
        return false;
    }
}
